package A一周刷爆LeetCode.A基础班.E链表;

/**
 * @author wei.zhao
 * @description: 将单向链表按某值划分成左边小、中间相等、右边大的形式
 * @date 2022年01月25日 15:29
 */
public class Code05_SmallerEqualBigger {

    public static void main(String[] args) {
        Node head = new Node(7);
        head.next = new Node(9);
        head.next.next = new Node(1);
        head.next.next.next = new Node(8);
        head.next.next.next.next = new Node(5);
        head.next.next.next.next.next = new Node(2);
        head.next.next.next.next.next.next = new Node(5);
        head = listPartition(head, 5);
        Code02_ReverseList.printLinkedList(head);
    }

    //六个变量，小于部分的头尾、等于部分的头尾、大于部分的头尾，最后串起来
    public static Node listPartition(Node head, int pivot) {
        Node bigHead = null;
        Node bigTail = null;
        Node smallHead = null;
        Node smallTail = null;
        Node equalHead = null;
        Node equalTail = null;
        //遍历节点
        while (head != null) {
            Node next = head.next;
            head.next = null;
            if (head.value > pivot) {
                if (null == bigHead) {
                    bigHead = head;
                    bigTail = head;
                } else {
                    bigTail.next = head;
                    bigTail = head;
                }
            } else if (head.value < pivot) {
                if (null == smallHead) {
                    smallHead = head;
                    smallTail = head;
                } else {
                    smallTail.next = head;
                    smallTail = head;
                }
            } else {
                if (null == equalHead) {
                    equalHead = head;
                    equalTail = head;
                } else {
                    equalTail.next = head;
                    equalTail = head;
                }
            }
            head = next;
        }
        //合成链表
        Node finalHead;
        if (null != smallHead) {
            finalHead = smallHead;
            if (equalHead != null) {
                smallTail.next = equalHead;
                equalTail.next = bigHead;
            } else {
                smallTail.next = bigHead;
            }
        } else if (null != equalHead) {
            finalHead = equalHead;
            equalTail.next = bigHead;
        } else {
            finalHead = bigHead;
        }
        return finalHead;
    }

}
